#include <bits/stdc++.h>
using namespace std;

class bint {
  // 常用类型重命名
  using u32 = unsigned int;
  using i64 = long long;
  using u64 = unsigned long long;
  // 静态常数
  static constexpr u64 BASE = 1e8;             // 进制数
  static constexpr int BIT = 8;                // 一个数字存储多少位，和进制对应
  static constexpr int FFT_LIMIT = 512;        // 超过阈值后使用 FFT
  static constexpr int NEWTON_LIMIT = 512;     // 超过阈值后使用牛顿迭代
  static constexpr int NEWTON_MIN_LEVEL = 16;  // 牛顿迭代的阈值
  static constexpr double PI = 3.14159265358979323846;  // 部分编译器无 M_PI 常数
  // 成员变量
  vector<u32> digits;
  int sign = 0;
  // 私有辅助类
  class DivisionByZeroError : public exception {
   public:
    const char *what() { return "binteger::Division By 0"; }
  };
  class FFT {
    using comp = complex<double>;
    static constexpr int FFT_BASE = 1e4;
    static vector<comp> w;
    static void init(int l) {
      int old = w.size();
      if (l <= (old << 1)) return;
      int t = __lg(l - 1);
      l = 1 << t, w[0] = 1.0, w.resize(l);
      for (int i = 1; i < l; i <<= 1) w[i] = polar(1.0, PI / (i << 1));
      for (int i = 1; i < l; i++) w[i] = w[i & (i - 1)] * w[i & -i];
    }
    static void dif(vector<comp> &x) {
      for (size_t l = x.size() >> 1, r = x.size(); l; l >>= 1, r >>= 1) {
        for (size_t k = 0; k < l; ++k) {
          comp a = x[k], b = x[k + l];
          x[k] = a + b, x[k + l] = a - b;
        }
        auto o = w.begin() + 1;
        for (size_t j = r; j < x.size(); j += r, ++o) {
          for (size_t k = j; k < j + l; ++k) {
            comp a = x[k], b = x[k + l] * (*o);
            x[k] = a + b, x[k + l] = a - b;
          }
        }
      }
    }
    static void dit(vector<comp> &x) {
      for (size_t l = 1, r = 2; l < x.size(); l <<= 1, r <<= 1) {
        for (size_t k = 0; k < l; ++k) {
          comp a = x[k], b = x[k + l];
          x[k] = a + b, x[k + l] = a - b;
        }
        auto o = w.begin() + 1;
        for (size_t j = r; j < x.size(); j += r, ++o) {
          for (size_t k = j; k < j + l; ++k) {
            comp a = x[k], b = x[k + l];
            x[k] = a + b, x[k + l] = (a - b) * conj(*o);
          }
        }
      }
    }
    static void fconv(vector<comp> &x, vector<comp> &y) {
      init(x.size()), dif(x), dif(y);
      double fx = 1.0 / x.size(), fx2 = 0.25 * fx;
      x[0] = {x[0].real() * y[0].real() + x[0].imag() * y[0].imag(),
              x[0].real() * y[0].imag() + x[0].imag() * y[0].real()};
      x[0] *= fx, x[1] *= y[1] * fx;

      for (size_t k = 2, m = 3; k < x.size(); k <<= 1, m <<= 1)
        for (size_t i = k, j = i + k - 1; i < m; ++i, j--) {
          comp oi = x[i] + conj(x[j]), hi = x[i] - conj(x[j]);
          comp Oi = y[i] + conj(y[j]), Hi = y[i] - conj(y[j]);
          comp r0 = oi * Oi - hi * Hi * ((i & 1) ? -w[i >> 1] : w[i >> 1]),
               r1 = Oi * hi + oi * Hi;
          x[i] = (r0 + r1) * fx2, x[j] = conj(r0 - r1) * fx2;
        }

      dit(x);
    }

   public:
    static void mul(vector<u32> &a, const vector<u32> &b) {
      int len1 = a.size();
      int len2 = b.size();
      int len = 2 << __lg(len1 + len2 - 1);
      vector<comp> x(len, 0.0);
      vector<comp> y(len, 0.0);
      for (int i = 0; i < len1; ++i)
        x[i] = comp(a[i] % FFT_BASE, a[i] / FFT_BASE);
      for (int i = 0; i < len2; ++i)
        y[i] = comp(b[i] % FFT_BASE, b[i] / FFT_BASE);

      FFT::fconv(x, y);

      a.resize(len1 + len2);
      u64 temp = 0;
      for (size_t i = 0; i < a.size(); ++i) {
        temp += (u64)(x[i].real() + 0.5) + (u64)(x[i].imag() + 0.5) * FFT_BASE;
        a[i] = temp % BASE;
        temp /= BASE;
      }
    }
  };
  // 私有成员变量
  void add(const vector<u32> &b) {
    if (b.size() > digits.size()) digits.resize(b.size());
    for (size_t i = 0; i < digits.size(); ++i) {
      if (i < b.size()) digits[i] += b[i];
      if (digits[i] >= BASE) {
        digits[i] -= BASE;
        if (i == digits.size() - 1) digits.push_back(0);
        digits[i + 1] += 1;
      } else if (i >= b.size()) {
        break;
      }
    }
    trim();
  }
  void trim() {
    while (digits.back() == 0 && digits.size() > 1) digits.pop_back();
    if (digits.size() == 1 && digits.back() == 0) sign = 0;
  }
  void sub(const vector<u32> &b) {
    int ret = cmp(b);
    if (ret == 0) {
      sign = 0;
    } else if (ret > 0) {
      // digits > b
      u32 carry = 0;
      for (size_t i = 0; i < digits.size(); ++i) {
        u32 minuend = carry;
        if (i < b.size())
          minuend += b[i];
        else if (carry == 0)
          break;
        if (digits[i] < minuend) {
          digits[i] = BASE + digits[i] - minuend;
          carry = 1;
        } else {
          digits[i] = digits[i] - minuend;
          carry = 0;
        }
      }
    } else {
      // digits < b
      sign = -sign;  // 注意符号取反
      digits.resize(b.size());
      u32 carry = 0;
      for (size_t i = 0; i < digits.size(); ++i) {
        if (b[i] < digits[i] + carry) {
          digits[i] = BASE + b[i] - digits[i] - carry;
          carry = 1;
        } else {
          digits[i] = b[i] - digits[i] - carry;
          carry = 0;
        }
      }
    }
    trim();
  }
  void mul(const vector<u32> &b) {
    int n = digits.size(), m = b.size();
    vector<u32> c(n + m);
    u64 temp = 0;
    for (int i = 0; i < n + m - 1; ++i) {
      for (int j = max(i - n + 1, 0); j <= min(i, m - 1); ++j) {
        temp += b[j] * (u64)(digits[i - j]);
      }
      c[i] = temp % BASE;
      temp /= BASE;
    }
    if (temp) c[n + m - 1] = temp;
    digits = c;
    trim();
  }
  void mul_fft(const vector<u32> &b) {
    FFT::mul(digits, b);
    trim();
  }
  void div2() {
    for (int i = size() - 1; i >= 0; i--) {
      if ((digits[i] & 1) && i) digits[i - 1] += BASE;
      digits[i] >>= 1;
    }
    trim();
  }
  void div(i64 b) {
    if (b == 0) throw DivisionByZeroError();
    if (*this == 0) return;
    if (b > INT_MAX) {
      *this = newton_divmod(b).first;
      return;
    }
    sign = (sign * b) > 0 ? 1 : -1;
    if (b == 2 || b == -2) {
      div2();
      return;
    }
    u64 cur = 0, div = std::abs(b);
    for (int i = size() - 1; i >= 0; --i) {
      cur = cur * BASE + digits[i];
      digits[i] = cur / div;
      cur %= div;
    }
    trim();
  }
  int cmp(const vector<u32> &b) const {
    if (digits.size() > b.size()) return 1;
    if (digits.size() < b.size()) return -1;
    for (int i = digits.size() - 1; i >= 0; --i) {
      if (digits[i] > b[i]) return 1;
      if (digits[i] < b[i]) return -1;
    }
    return 0;
  }
  int cmpWithSign(const bint &b) const {
    if (sign != b.sign) return sign > b.sign ? 1 : -1;
    if (sign == 0) return 0;  // zero
    return sign * cmp(b.digits);
  }
  bint abs() const {
    bint res = *this;
    res.sign = 1;
    return res;
  }
  int size() const { return digits.size(); }
  void resize(int n) { digits.resize(n); }
  bint move_l(int d) const {
    if (sign == 0) return *this;
    if (d == 0) return *this;
    bint res;
    res.sign = sign;
    res.digits.reserve(size() + d + 1);
    for (int i = 1; i <= d; ++i) res.digits.push_back(0);
    for (int i = 0; i < size(); ++i) {
      res.digits.push_back(digits[i]);
    }
    return res;
  }
  bint move_r(int d) const {
    if (sign == 0 || d >= size()) return 0;
    if (d == 0) return *this;
    bint res;
    res.sign = sign;
    res.digits.reserve(size() - d + 1);
    for (int i = d; i < size(); ++i) {
      res.digits.push_back(digits[i]);
    }
    return res;
  }
  bint newton_inv(int n) const {
    if (*this == 0) throw DivisionByZeroError();
    if (min(size(), n - size()) <= NEWTON_MIN_LEVEL) {
      bint a;
      a.resize(n + 1);
      a.sign = 1;
      a.digits.back() = 1;
      return a.divmod(*this, false).first;
    }
    int k = (n - size() + 2) >> 1;
    int k2 = k > size() ? 0 : size() - k;
    bint x = move_r(k2);
    int n2 = k + x.size();
    bint y = x.newton_inv(n2);
    bint a = y + y;
    bint b = (*this) * y * y;
    return a.move_l(n - n2 - k2) - b.move_r(2 * (n2 + k2) - n) - 1;
  }
  pair<bint, bint> newton_divmod(const bint &x) const {
    int k = size() - x.size() + 2;
    int k2 = k > x.size() ? 0 : x.size() - k;
    bint x2 = x.move_r(k2);
    if (k2 != 0) x2 += 1;
    int n2 = k + x2.size();
    bint u = (*this) * x2.newton_inv(n2);
    bint q = u.move_r(n2 + k2);
    bint r = (*this) - q * x;
    while (r >= x) q += 1, r -= x;
    return {q, r};
  }
  pair<bint, bint> divmod(const bint &x, bool enable_newton = true) const {
    if (x == 0) throw DivisionByZeroError();
    if (sign == 0) return {0, 0};
    bint a = abs(), b = x.abs();
    if (a < b) return {0, sign == 1 ? a : -a};
    if (enable_newton && size() > NEWTON_LIMIT) return newton_divmod(x);
    int t = BASE / (x.digits.back() + 1);
    a *= t, b *= t;
    int n = a.size(), m = b.size();
    bint q = 0, r = 0;
    q.resize(n);
    for (int i = n - 1; i >= 0; --i) {
      r *= BASE, r += a.digits[i];
      int d1 = m - 1 < r.size() ? r.digits[m] : 0,
          d2 = m - 2 < r.size() ? r.digits[m - 1] : 0;
      int d = (d1 * BASE + d2) / b.digits[m - 1];
      r -= b * d;
      while (r.sign < 0) r += b, d--;
      q.digits[i] = d;
    }
    q.sign = sign * x.sign;
    q.trim();
    return {q, r / t};
  }
  vector<char> to_bin() const { // low -> high
    vector<char> ret;
    for (bint x = *this; x != 0; x.div2()) ret.emplace_back(x.digits[0] & 1);
    return ret;
  }
  template<class T>
  void bin_op(const bint &b, const T &op) {
    vector<char> x = to_bin(), y = b.to_bin();
    int l1 = x.size(), l2 = y.size(), len = max(l1, l2);
    vector<char> ret(len, 0);
    for (int i = 0; i < len; ++i) {
      ret[i] = op(i < l1 ? x[i] : 0, i < l2 ? y[i] : 0);
    }
    reverse(ret.begin(), ret.end());
    *this = ret;
  }

 public:
  // 构造函数
  bint() { *this = 0; }
  bint(i64 x) { *this = x; }
  bint(const string &s) { *this = s; }
  bint(const vector<char> &b) { *this = b; }
  // 常用运算符重载
  bint &operator=(i64 x) {
    if (x == 0) return sign = 0, *this;
    if (x == LLONG_MIN) return *this = "-9223372036854775808";
    sign = (x > 0) ? 1 : -1;
    digits.clear();
    u64 n = x;
    do {
      digits.push_back(n % BASE), n /= BASE;
    } while (n);
    return *this;
  }
  bint &operator=(const string &s) {
    if (s.empty()) return *this = 0;
    int start = 0;
    sign = 1;
    if (s[0] == '-') sign = -1, ++start;
    digits.clear();
    for (int i = s.size() - BIT; i >= start - BIT + 1; i -= BIT) {
      u32 temp = 0;
      for (int j = max(start, i); j < i + BIT; j++) {
        temp = temp * 10 + s[j] - '0';
      }
      digits.push_back(temp);
    }
    if (size() == 1 && digits.back() == 0) sign = 0;
    return *this;
  }
  bint &operator=(const vector<char> &b) { // high -> low
    *this = 0;
    bint pow2 = 1;
    for (int i = b.size() - 1; i >= 0; --i, pow2 += pow2)
      if (b[i]) *this += pow2;
    return *this;
  }
  bool operator==(const bint &b) const {
    if (sign != b.sign) return false;
    if (sign == 0) return true;
    return cmp(b.digits) == 0;
  }
#if __cplusplus >= 202002L  // c++20 只需要重载 <=>
  int operator<=>(const bint &b) const { return cmpWithSign(b); }
#else  // 兼容低版本 c++11
  bool operator<(const bint &b) const { return cmpWithSign(b) < 0; }
  bool operator<=(const bint &b) const { return cmpWithSign(b) <= 0; }
  bool operator>(const bint &b) const { return cmpWithSign(b) > 0; }
  bool operator>=(const bint &b) const { return cmpWithSign(b) >= 0; }
  bool operator!=(const bint &b) const { return cmpWithSign(b) != 0; }
#endif
  bint &operator+=(const bint &b) {
    // this += 0 -> this
    if (b.sign == 0) return *this;
    // 0 += b -> b;
    if (sign == 0) {
      *this = b;
      return *this;
    }
    if (sign == b.sign) {
      // 符号相等，直接相加
      add(b.digits);
      return *this;
    }
    // 符号不相等，直接相减
    sub(b.digits);
    return *this;
  }
  bint &operator-=(const bint &b) {
    // this -= 0 -> this
    if (b.sign == 0) return *this;
    // 0 -= b -> -b;
    if (sign == 0) {
      *this = b;
      sign = -sign;
      return *this;
    }
    if (sign != b.sign) {
      // 符号不相等，直接相加
      add(b.digits);
      return *this;
    }
    // 符号相等，直接相减
    sub(b.digits);
    return *this;
  }
  bint &operator*=(const bint &b) {
    if (b.sign == 0 || sign == 0) {
      sign = 0;
      return *this;
    }
    sign *= b.sign;
    if (digits.size() * b.digits.size() <= FFT_LIMIT)
      mul(b.digits);
    else
      mul_fft(b.digits);
    return *this;
  }
  bint &operator/=(const bint &b) { return *this = divmod(b).first; }
  bint &operator/=(i64 b) { return div(b), *this; }
  bint &operator%=(const bint &b) { return *this = divmod(b).second; }
  bint &operator%=(i64 b) { return *this -= (*this / b * b); }
  bint &operator&=(const bint &b) {
    bin_op(b, [](char lhs, char rhs) { return lhs & rhs; });
    return *this;
  }
  bint &operator|=(const bint &b) {
    bin_op(b, [](char lhs, char rhs) { return lhs | rhs; });
    return *this;
  }
  bint &operator^=(const bint &b) {
    bin_op(b, [](char lhs, char rhs) { return lhs ^ rhs; });
    return *this;
  }
  bint &operator<<=(i64 b) {
    if (*this == 0) return *this;
    while (b--) *this += *this;
    return *this;
  }
  bint &operator>>=(i64 b) {
    for (; b--; div2())
      if (*this == 0) return *this;
    return *this;
  }
  bint &operator++() { return *this += 1; }
  bint &operator--() { return *this -= 1; }

  bint operator+(const bint &b) const { return bint(*this) += b; }
  bint operator-(const bint &b) const { return bint(*this) -= b; }
  bint operator*(const bint &b) const { return bint(*this) *= b; }
  bint operator/(const bint &b) const { return divmod(b).first; }
  bint operator/(i64 b) const { return bint(*this) /= b; }
  bint operator%(const bint &b) const { return divmod(b).second; }
  bint operator%(i64 b) const { return bint(*this) %= b; }
  bint operator&(const bint &b) { return bint(*this) &= b; }
  bint operator|(const bint &b) { return bint(*this) |= b; }
  bint operator^(const bint &b) { return bint(*this) ^= b; }
  bint operator<<(i64 b) { return bint(*this) <<= b; }
  bint operator>>(i64 b) { return bint(*this) >>= b; }
  bint operator++(int) {
    bint ret = *this;
    return *this += 1, ret;
  }
  bint operator--(int) {
    bint ret = *this;
    return *this -= 1, ret;
  }
  bint operator-() const {
    if (*this == 0) return 0;
    bint res = *this;
    res.sign = -res.sign;
    return res;
  }
  bool operator!() { return *this == 0; }
  bool operator&&(bool rhs) { return rhs && (*this != 0); }
  bool operator||(bool rhs) { return rhs || (*this != 0); }
  // 友元函数：输入输出，整形在前的算数运算
  friend ostream &operator<<(ostream &os, const bint &a) {
    if (a.sign == 0) return os << "0", os;
    if (a.sign < 0) os << "-";
    os << setfill('0') << a.digits.back();
    for (int i = a.digits.size() - 2; i >= 0; i--) {
      os << setw(BIT) << a.digits[i];
    }
    return os;
  }
  friend istream &operator>>(istream &is, bint &a) {
    string str;
    is >> str;
    a = str;
    return is;
  }
  // 强制转 long long，如果用于普通整型的计算，可以去掉 explicit
  explicit operator long long() {
    long long res = 0;
    for (int i = min(2, size() - 1); i >= 0; --i) {
      res = res * BASE + digits[i];
    }
    return res * sign;
  }
  vector<char> to_binary() { // high to low
    vector<char> ret = to_bin();
    reverse(ret.begin(), ret.end());
    return ret;
  }
  // 快速平方、开方
  bint pow(u64 x) {
    bint res = 1;
    for (bint a(*this); x; x >>= 1, a *= a) {
      if (x & 1) res *= a;
    }
    return res;
  }
  bint root(u64 x) {
    if (sign == 0 || x == 1) return *this;
    bint n = *this, t = BASE, ret = min(n, t.move_l((n.digits.size() + x) / x));
    int l = 0, r = BASE - 1;
    while (l < r) {
      int mid = (l + r) >> 1;
      ret.digits.back() = mid;
      if (ret.pow(x) <= n)
        l = mid + 1;
      else
        r = mid;
    }
    ret.digits.back() = l;
    ret.trim();
    bint x2 = (ret * (x - 1) + n / ret.pow(x - 1)) / x;
    while (x2 < ret) {
      swap(x2, ret);
      x2 = (ret * (x - 1) + n / ret.pow(x - 1)) / x;
    }
    return ret;
  }
};
// 辅助类中的静态成员
vector<complex<double>> bint::FFT::w{1.0};

/**
 * 测试模版 luogu
 * P1601 加法
 * P2142 减法
 * P1303 普通乘法
 * P1480 除整数
 * P1919 FFT 乘法
 * P2293 开根号(内部使用了牛顿迭代除法)
 * 
 * P1896 直接用插头DP写法测试位运算，关掉 explicit 直接当 long long 使用
 */
void exgcd(bint a, bint b, bint&x, bint&y) {
  if (!b) {
    x = 1, y = 0;
  } else {
    exgcd(b, a % b, y, x);
    y -= (a / b) * x;
  }
}
int main() {
  bint a, b, x, y;
  cin >> a >> b;
  exgcd(a, b, x, y);
  cout << (x + b) % b << endl;
}